﻿/**
 * This file contains the core javascript needed for benchmarking an algorithm.
 * @dependencies none
 */

/**
 * A BenchmarkSuite represents a set of benchmarkable algorithms and their properties.
 * @constructor
 */
BenchmarkSuite = function() {

	var suiteMap = new Object();
	var renderer;
	var thisReference = this;
	var nArray;
	var repetitions;
	
	/**
	 * Add an entry to the suite. The input generator and the algorithm will be bound together. 
	 * I.e., the the input generator will provide the input to the algorithm.
	 *
	 * @param {String} algorithmName the identifier
 	 * @param {InputGenerator} an input generator
	 * @param {Algorithm} an algorithm
	 */
	this.add = function(algorithmName, inputGenerator, algorithm) {
		suiteMap[algorithmName] = {
			inputGenerator: inputGenerator,
			algorithm: algorithm
		}
		renderer.renderAddAlgorithm(algorithm);
	}

	/**
	 * Remove an item from the suite.
	 * @param {Number} idToRemove the id
	 */
	this.remove = function(idToRemove) {
		renderer.renderRemoveAlgorithm(suiteMap[idToRemove]['algorithm']);
		suiteMap[idToRemove] = null;
	}

	/**
	 * @param {BenchmarkSuite.Renderer} the renderer for this suite
	 */
	this.setRenderer = function(r) {
		renderer = r;
		renderer.setBenchmarkSuite(thisReference);
	}

	/**
	 * Initialize the suite.
	 */
	this.init = function() {
		renderer.renderInit();
	}

	/**
	 * @return {Object} the suite's data
	 */
	this.getSuite = function() {
		return suiteMap;
	}

	/**
	 * @param {Object} properties [nArray|repetitions]
	 */
	this.setBenchmarkParams = function(paramProperties) {
		nArray = paramProperties['nArray'];
		repetitions = paramProperties['repetitions'];
	}	

	/**
	 * Run the benchmarks in the suite.
	 * @return {Array{Array{BenchmarkResults}}} the results
	 */
	this.runBenchmarks = function() {
		var suiteResults = new Array();

		for (var entry in suiteMap) {
			var perAlgorithmResults = new Array();
			for (var i = 0; i < nArray.length; i++) {
				perAlgorithmResults.push(
					benchmark(suiteMap[entry]['algorithm'], 
						  suiteMap[entry]['inputGenerator'], 
						  nArray[i], 
						  repetitions)); // Do benchmark
			}
			suiteResults.push(perAlgorithmResults);			
		} 

		return suiteResults;
	}
}

/**
 * Instances render a BenchmarkSuites.
 * @param {BenchmarkSuite.Renderer.SingleAlgorithmRenderer} singleAlgorithmRenderer - renders a html representation of a single algorithm
 * @param {BenchmarkSuite.Renderer.SuiteContainerRenderer} suiteContainerRenderer - renders a html representation of the suite container
 * @constructor
 */
BenchmarkSuite.Renderer = function(singleAlgorithmRenderer, suiteContainerRenderer) {
	var benchmarkSuite;

	/**
	 * @param {BenchmarkSuite} the suite
	 */
	this.setBenchmarkSuite = function(bSuite) {
		benchmarkSuite = bSuite;
	}

	/**
	 * Render the initial view.
	 */
	this.renderInit = function() {
		suiteContainerRenderer.renderInitContainer();
	}

	/**
	 * Render an added Algorithm.
	 * @param {Algorithm}
	 */
	this.renderAddAlgorithm = function(addedAlgorithm) {
		singleAlgorithmRenderer.renderAdd(addedAlgorithm);
	}

	/**
	 * Render removing an algorithm
	 * @param {Algorithm}
	 */
	this.renderRemoveAlgorithm = function(removedAlgorithm) {
		singleAlgorithmRenderer.renderRemove(removedAlgorithm);
	}
}

/**
 * Render an algorithm in the suite.
 * @param {Object} properties [algorithmAddRenderer,algorithmRemoveRenderer]
 * @constructor
 */
BenchmarkSuite.Renderer.SingleAlgorithmRenderer = function(properties) {

	/**
	 * @param {Algorithm} the algorithm added to the suite
	 */
	this.renderAdd = function(algorithm) {
		properties['algorithmAddRenderer'](algorithm); 
	}

	/**
	 * @param {Algorithm} the algorithm removed from the suite
	 */
	this.renderRemove = function(algorithm) {
		properties['algorithmRemoveRenderer'](algorithm); 
	}
}

/**
 * Render a suite.
 * @param {Object} properties [initialRenderer]
 * @constructor
 */
BenchmarkSuite.Renderer.SuiteContainerRenderer = function(properties) {
	this.renderInitContainer = function() {
		properties['initialRenderer']();
	}
}

/**
 * An input generator.
 * @param inputGenerator {Function} a function which will generate input with the given n {int} parameter
 * @constructor 
 */			
InputGenerator =  function(inputGenerator) {
	this.generateInput = inputGenerator;
}

/**
 * A class for representing an algorithm.
 *
 * @param runnable {Function} the function on which run() will be invoked
 * @param {Object} properties: [name, description]
 * @constructor
 */
Algorithm =  function(runnable, properties) {
	this.run = runnable;
	this.getName = function() { return properties['name']; }
	this.getDescription = function() { return properties['description']; }
}

/**
 * A data class that represents a benchmark result.
 *
 * @param {int} n the n
 * @param {Object} output the output
 * @param {RunningTimeInfo} runningTimeInfo an instance of BenchmarkResults.RunningTimeInfo
 * @constructor
 */
BenchmarkResults = function(n, output, runningTimeInfo) {
	this.getN = function () { return n; }
	this.getOutput = function () { return output; }
	this.getRunningTimeInfo = function () { return runningTimeInfo; }
}

/**
 * A data class that represents a benchmark's running time statistics.
 *
 * @param runningTimes {Array} an array of milliseconds, each of which represents a running time of a benchmark
 * @constructor
 */ 
BenchmarkResults.RunningTimeInfo = function(runningTimes) {
	var min = Math.min.apply( Math, runningTimes );
	var max = Math.max.apply( Math, runningTimes );

	var sum = 0;
	for	(var i = 0; i < runningTimes.length;i++) {
		sum += runningTimes[i];
	}
	var avg = Math.round(sum / runningTimes.length);

	var sorted = runningTimes.sort(function(a,b){return a - b}); // Numerical order, not alphabetical.
	var median;
	if (sorted.length % 2 == 0) { // Even
		median = (sorted[sorted.length/2-1] + sorted[sorted.length/2]) / 2;
	} else { // Odd
		median = sorted[Math.floor(sorted.length/2)];
	}
	median = Math.round(median);

	this.getMin = function() { return min; }
	this.getMax = function() { return max; }
	this.getAverage = function() { return avg; }
	this.getMedian = function() { return median; }
	this.getRunningTimes = function() { return sorted; }
}

/**
 * @param {Object} chartConfig an object containing chart configuration props
 * @param {Array} benchmarkResults an array of arrays, of which each represents a benchmark result of a distinct algorithm
 * @return {String} an url of the chart image for the benchmark results array	
 */
buildChartUrl = function(chartConfig, benchmarkResults) {
	/**
 	 * @return {Array} data sets representing x & y properties of a benchmark result
	 */
	var buildDataSets = function() {
		var dataSetsArray = new Array();

		for (var i = 0; i < benchmarkResults.length;i++) { // Loop an array containing arrays of BenchmarkResult instances
			benchmarkResultsArray = benchmarkResults[i];

			var xValues = new Array(); // n
			var yValues = new Array(); // sorting time
	
			for (var j = 0; j < benchmarkResultsArray.length; j++) { // An array of BenchmarkResult instances 
				xValues.push(benchmarkResultsArray[j].getN());
				yValues.push(benchmarkResultsArray[j].getRunningTimeInfo().getMedian());
			}
		
			var maxX = Math.max.apply( Math, xValues );
			var minX = Math.min.apply( Math, xValues );
			var maxY = Math.max.apply( Math, yValues );
			var minY = Math.min.apply( Math, yValues );

			dataSetsArray.push({ 
					minX: minX, 
					minY: minY,
					maxX: maxX,
					maxY: maxY,
					xValues: xValues,
					yValues: yValues
				      });
		}
		return dataSetsArray;
	}

	/**
  	 * @return {Number} the min or max of the given property within the data set
	 */
	var calculateMinOrMax = function(dataSets, property, isMin) {
		var values = new Array();
		for (i = 0; i < dataSets.length; i++) {
			values.push(dataSets[i][property]);
		}
		return isMin == 'min' ? Math.min.apply( Math, values ) : Math.max.apply( Math, values ); // Min or Max of the values
	}

	/**
	 * @return values for the google chart chd parameter
	 * @see http://code.google.com/apis/chart/formats.html#data_scaling
	 */
	var buildChdParam = function(dataSets) {
		var dataSetString = ""; // e.g., "xvalues|yvalues|x2values|y2values"
		for (i = 0; i < dataSets.length; i++) {
			dataSetString += dataSets[i].xValues + "|" + dataSets[i].yValues;
			if (!(i == (dataSets.length - 1))) // Not the last data set yet?
				dataSetString += "|";
		}	
		return dataSetString;
	}

	/**
	 * @return values for the google chart chds (scaling) parameter
	 * @see http://code.google.com/apis/chart/formats.html#data_scaling
	 */
	var buildChdsParam = function(dataSets) {
		var dataSetScalingValues = ""; // e.g., "minX,maxX,minY,maxY,minX2,maxX2,minY2,maxY2"
		for (var i = 0; i < dataSets.length; i++) {
			dataSetScalingValues += dataSets[i]['minX'] + "," + dataSets[i]['maxX'] + "," + dataSets[i]['minY'] + "," + dataSets[i]['maxY'];
			if (!(i == (dataSets.length - 1))) // Not the last data set yet?
				dataSetScalingValues += ",";
		}
		return dataSetScalingValues;
	}

	var dataSets = buildDataSets();
	var minX = calculateMinOrMax(dataSets, "minX", "min");
	var minY = calculateMinOrMax(dataSets, "minY", "min");
	var maxX = calculateMinOrMax(dataSets, "maxX", "max");
	var maxY = calculateMinOrMax(dataSets, "maxY", "max");
	var chartResolution = chartConfig && chartConfig['resolution'] ? chartConfig['resolution'] : "300x300";

	var urlBase = "http://chart.apis.google.com/chart?";
	var constantParams = "cht=lxy&chxt=x,y&chs="+chartResolution;
	var axisScaleParam = "&chxr=0,0,"+maxX +"|1,0,"+maxY; 
	var axisLabelsParam = "&chxl=0:|0|n"+maxX+"|1:||"+maxY+" ms";
	var scalingParam = "&chds="+buildChdsParam(dataSets);
	var dataParam = "&chd=t:" + buildChdParam(dataSets);

	return urlBase + constantParams + axisScaleParam  + axisLabelsParam +
		dataParam +
		scalingParam;
}

/**
 * A function for performing the benchmark operation.
 *
 * @param algorithm {Algorithm} the algorithm to benchmark
 * @param inputGenerator {InputGenerator} the input generator
 * @param n {int} the n
 * @param repetitions {int} how many times the benchmark should be repeated
 * @return {BenchmarkResults} the results
 * @static
 */
benchmark = function(algorithm, inputGenerator, n, repetitions) {
	if (!repetitions) {
		repetitions = 1;
	}

	var input = inputGenerator.generateInput(n);

	var averageRunningTime;
	var output;

	var minRT = Number.MAX_VALUE;
	var maxRT = 0;

	var runningTimes = new Array();

	for (var i = 0; i < repetitions ; i++) {
		var start = (new Date()).getTime();
		output = algorithm.run(input);
		var end = (new Date()).getTime();
		runningTimes.push((end-start));
	}

	return new BenchmarkResults(n, output, new BenchmarkResults.RunningTimeInfo(runningTimes));
}